\subsection{提名协议}\label{sec:scp_nominate}

因为仅仅要求{\slot}是偏序的，一些SCP的应用讲对每个{\slot}来说将只有一个貌似可信的表决。例如，在认证透明性中，每个中心认证机构可能有一系列它自己的{\slot}并且对每个{\slot}只签署唯一一份认证树。然而，其它一些应用承认一个{\slot}有多个貌似可信的值，这种情形对减少可能的输入值是有帮助的。我们的策略是从一个基于某种超时假设的可以获得共识的同步提名协议出发，并把提名协议的输出运用到一个安全性不依赖于时间的异步表决协议中~\cite{Lamport:2011:BAL:2075029.2075043}。这样一个初始同步的阶段有时候被称为\textit{调解者}(conciliator，~\cite{Aspnes:2010:MAS:1835698.1835802})。

提名协议通过``关于一个{\slot}的候选值趋于相同''得以运作。之后节点确定性地将这些候选值组合起来成{\slot}的一个单独\textit{合成}值。具体如何组合这些值取决于应用场景。举例而言，恒星网络使用SCP为每个{\slot}选择了一个事务集合和一个分类帐时间戳。为了组合这些候选值，恒星网络选择了这些事务集的并以及它们的时间戳的最大值。(含有无效的时间戳的值不会接受足够多的提名，从而不会变成候选者。)其它可能的方法包括，通过取集合交来组合集合，或者简单地选择那些有最大哈希值的候选者。

节点通过对陈述$nominate\;x$进行联邦选举产生出一个候选值$x$。

\begin{definition}[候选的]
当一个节点$v$确认了关于值$x$的陈述$nominate\;x$——即$v$批准了$accept(nominate\;x)$, 它则认为$x$是\textbf{候选的}。
\end{definition}

只要节点$v$没有候选值，$v$就有可能投票赞成$nominate\;x$，这里的$x$可以是任何通过了应用层有效性检验(例如时间戳不能是未来时间点)的值。事实上，一般而言$v$应当重新提名它可观察到的其它节点提名的任何值，不过会有一些防止候选者激增的限制(下文将会讨论)。一旦$v$有了候选值之后，它必须停止对任何新的$x$的值的陈述$nominate\;x$进行投票。但是如联邦选举过程规定的那样，它仍然应当接受为新的值产生的$nominate$陈述(当被{\vblock}集合接受时)并确认新的$nominate$陈述。

当一个系统有完好节点的时候(这意味着它已避免了完全的错误)提名协议有一些属性。特别地，对每个{\slot}来说：
\begin{enumerate}
	\item\label{enum:cand_p1} 完好节点至少可以产生一个候选值。
	\item\label{enum:cand_p2} 在某一时刻，可能的候选值集合停止增长。
	\item\label{enum:cand_p3} 如果任意一个完好节点认为$x$是一个候选值的话，那么最终所有的完好节点都会认为$x$是一个候选值。
\end{enumerate}

现在考虑提名协议是如何达到这三个属性的。属性\ref{enum:cand_p1}可以满足是因为$nominate$陈述是不可辩驳的。节点从不会投票反对提名某个特别的值，且直到第一个候选值被确认为止完好节点可以提名任何值。只要有任何值通过了应用层的有效性检查，完好节点就可以投票赞成并确认$nominate\;x$。属性\ref{enum:cand_p2}可以保证，这是因为每个完好节点至少可以确认一个候选值——这会在一个有限时间内发生——不会有任何节点投票赞成新的值。因此，可能会成为候选值的只有那些已经被那些完好节点投票赞成的值。属性\ref{enum:cand_p3}是定理\ref{thm:confirmed_stats_keep_liveness}的直接结果。

如果参与的值组合变少那么提名过程将会更为高效。因此，我们给节点指派一个暂时的优先级，并且如果可能的话让每个节点提名相同值的节点为更高优先级节点。更具体地讲，设$H$是一个加密哈希函数{\footnote{译注：加密哈希函数需要保证下面两者在计算上不可行：1)找到被加密消息(原像)；2)找到和原像不同但有相同哈希值的消息。常见的算法有MD5，SHA-1，SHA-2，SHA256等。}}，其值域是一个整数集合$\left\{0,\dots,h_{max}-1\right\}$。($H$可能是SHA-256~\cite{shs2015}，在这种情形下$h_{max}=2^{256}$。)令$G_i(m)=H(i, x_{i-1},m)$是一个特别用于{\slot}的哈希函数，这里的$x_{i-1}$是为$i$之前的{\slot}选用的值(或者当{\slot}存在偏序时{\slot}$i$直接依赖的值的有序集合)。给定一个{\slot}$i$和一个轮计数值$n$，每个节点按照如下公式计算它的\textit{邻居}以及为它的每个邻居计算\textit{优先级}。

\begin{equation*}
	weight(v,v^{\prime}) = \frac{|\left\{q|q\in\mybm{Q}(v)\wedge v^{\prime}\in q\right\}|}{|\mybm{Q}(v)|}
\end{equation*}

\begin{equation*}
	neighbors(v,n) = \left\{v^{\prime}|G_i(N,n,v^{\prime})<h_{max}\cdot weight(v,v^{\prime})\right\}
\end{equation*}

\begin{equation*}
	priority(n,v^{\prime}) = G_i(P,n,v^{\prime})
\end{equation*}

$N$和$P$是生成两个不同哈希函数的常量。函数$weight(v,v^{\prime})$返回$\mybm{Q}$中包含$v^{\prime}$的切片数占总切片数的百分比。通过考量$v^{\prime}$的权重作为概率的方式作用于$n$产生邻居$neighbors(v,n)$，我们也减少了不具很多信任的节点仍然可以支配某一轮的可能性。

每个节点$v$最初应当找到一个节点$v_0\in neighbors(v,0)$使得它可以在它可以通信的节点间最大化$priority(0,v_0)$，然后投票赞成$nominate$和$v_0$相同的值。只有当$v=v_0$时$v$应当引入一个新的值来提名。$v$应当使用超时来决定新的用于投票赞成的$nominate$陈述。$n$次超时后，$v$应当找到一个节点$v_n\in neighbors(v,n)$来最大化$priority(n,v_n)$，且提名每个$v_n$所提名的值。

\begin{theorem}\label{thm:intact_have_same_value}
	最终所有的完好节点将有相同的合成值。
\end{theorem}

\begin{proof}
	这一定理的证明可由提名协议的三个性质而得。每个完好节点只会提名一个有限的表决。在没有恶性行为节点的情形下，完好节点将会在一个相同的候选值集合$Z$上收敛。为了阻止该收敛，恶性行为节点可能会引入新的候选值，在某个时间点上它可能是某些但不是所有的完好节点的候选者。这些候选者将需要获得从完好节点那里的选票，然而这使得它们是一个有限集合。最终恶性行为节点或者会停止扰乱系统，或者用尽它们注入的新候选值，在这两种情形下完好节点会在$Z$上收敛。
\end{proof}

\subsubsection{具体的提名协议}\label{sec:scp_nominate_concrete}

\begin{figure}
\begin{tabu}{rX<{\vrule width 0pt height 0pt depth 1.5ex}}
\toprule
    \rowfont\bfseries 变量 & \multicolumn{1}{l}{含义} \\
\midrule
$X$ & 节点$v$已提名的值集合 \\

$Y$ & 节点$v$已承认是为已提名的值集合\\

$Z$ &节点$v$认为是候选值的集合\\

$N$ & 接收自每个节点的最新的\textit{提名}类消息
each node \\[-.5ex] \bottomrule
\end{tabu}
  \caption{节点$v$为每个{\slot}维护的提名状态}
  \label{fig:nomstate}
\end{figure}

\begin{figure}
{\centering\abovedisplayskip4pt
\belowdisplayskip4pt
\begin{tikzpicture}
  \node[draw=few-\maincolor-bright,thick,
    text width=\textwidth-24pt, align=justify,
    outer sep=0pt,
    inner xsep=12pt, inner ysep=-6pt]
       {
  \begin{description}[style=nextline,leftmargin=2ex]
  \item[\mdseries \textit{提名}~$v~i~X~Y~D$]
%
这是一个从节点$v$为{\slot}~$i$提名值的消息。$D$是$v$的{\quorum}切片$\mybm{Q}(v)$或是$\mybm{Q}(v)$的无碰撞冲突的哈希。$X$和$Y$来自$v$的状态。这些具体的消息编码了下面抽象的消息:
%
{%\parskip=0pt
\begin{itemize}[topsep=4pt,itemsep=4pt]
  \item $\{\, \emph{nominate}~x \mid x\in X\,\}$
    \hfill (投票赞成$X$中的每个值)
  \item $\{\, \confirm{\emph{nominate}~x} \mid x\in Y\,\}$
%    \hfill (votes to confirm nominations in $Y$)
\end{itemize}
}
\medskip
\end{description}
};
\end{tikzpicture}}
\caption{提名协议中的消息}
\label{fig:nommsg}
\end{figure}

{图\ref{fig:nomstate}}列出了一个节点$v$必须为每个{\slot}维护的提名协议状态。$X$是$v$已投票赞成$nominate\;x$的值$x$的集合，$Y$是$v$已接受$nominate\;x$的值集合，$Z$是候选值集合——即含$v${\quorum}已经声明$accept(nominate\;x)$的所有值。最后，$v$维护$N$——来自每个节点的最新值。(技术上来讲，$X$，$Y$和$Z$可以从$N$的值中重新算出来，但能直接引用它们的值是方便的。)所有的这些域最初都被初始化为空集。注意到$X$，$Y$和$Z$都总随时间的推移而增长——节点不会从这些集合中删除元素。

{图\ref{fig:nommsg}}说明了一个包含提名协议的具体消息。由于$X$和$Y$随时间单调递增，决定在不考虑网络发送顺序的情况下来自相同节点的多个\textsl{NOMINATE}消息哪个是最新的是可能的——只要$D$不改变中间提名(mid-nomination；否则必须记录$D$的版本信息)。只有一个远程过程调用(RPC)对提名来说是必要的——参数是发送者的最新\textsl{NOMINATE}消息而返回值是接受者的(最新\textsl{NOMINATE}消息{\todo{可能是accept消息，不确定}})。如果$D$或被提名值是加密哈希值，必要时第二个RPC应当允许获取没有缓存的哈希原像。

由于节点无法通过任何手段知道提名协议何时完成，$SCP$必须在不同的节点处处理不同的合成值。则有这样一种优化，节点可在它们有候选值之前尝试预测最终的合成值。为此，合成值可以在$Z\neq \emptyset$时设为$combine(Z)$，否则在$Y\neq \emptyset$时设为$combine(Z)$，否则在$X\neq \emptyset$时设为$combine(X)$。这意味着高优先级节点可以在提名的同时初始化表决，在它的第一个\textsl{NOMINATE}消息上加上第一个表决消息\textsl{PREPARE}(表述参见下文)。